package example2;

import java.util.HashMap;
import java.util.Map;

public class LeetCode169 {
    public static void main(String[] args) {

    }
}

class Solution169 {
    /**
     * 方法四：Boyer-Moore 投票算法     (这个得举例子好好想想)
     * 遍历数组，对每个数做如下操作：如果count==0，那么就将当前数赋值给候选数temp，
     * 如果当前数等于候选数，那么count++，如果不等于，那么count--，因为根据题目要求，一定存在众数，
     * 也就是数量大于 n/2的，那么最后count一定大于0，那么遍历结束，候选数就是众数
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int temp = nums[0];
        int count = 1;
        for(int i=1;i<nums.length;i++){
            if(count == 0){
                temp = nums[i];
            }
            if(temp == nums[i]){
                count++;
            }else{
                count--;
            }
        }
        return temp;
    }

    //方法三：通过分治的方法，把数组分为两部分，选出两部分的众数，如果相同，就是整体的众数，不同再比较次数，递归处理
    //方法二：可以排序后取 n/2下表位置的元素一定是众数

    /**
     * 方法一：hash表
     * @param nums
     * @return
     */
    public int majorityElement1(int[] nums) {
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Integer num = map.get(nums[i]);
            if (num == null) {
                num = 0;
            }
            num++;
            if(num > n/2)   return nums[i];
            map.put(nums[i],num);
        }
        return 0;
    }
}
